Maximale snede

In de grafentheorie is een maximale snede een snede met maximale grootte of gewicht.

Voor een niet-gerichte graaf ${\displaystyle G=(V,E)}$ met knopenverzameling ${\displaystyle V}$ en kantenverzameling ${\displaystyle E}$, waarbij aan elke kant ${\displaystyle (i,j)\in E}$ een gewicht ${\displaystyle w_{ij}}$ is toegekend, is een maximale snede een partitie van ${\displaystyle V}$ in twee delen ${\displaystyle S,T}$, zodanig dat de som van de gewichten van de kanten tussen ${\displaystyle S}$ en ${\displaystyle T}$ maximaal is.

Het probleem van het vinden van een maximale snede heet in het Engels max-cut problem en is een klassiek probleem uit de grafentheorie. Het is niet enkel theoretisch van belang. Het komt voor bij het ontwerpen van de lay-out van grote geïntegreerde schakelingen en in statistische natuurkunde.^[1]

1. ↑ Francisco Barahona, Martin Grötschel, Michael Jünger, Gerhard Reinelt, "An application of combinatorial optimization to statistical physical and circuit layout design." Operational Research (1988), vol. 36, nr. 3, blz. 493–513